/**
 *
 * @file
 *		heap_julia
 *
 * @brief
 *		Heap implementation by julia
 */

#include "../../api/heap.h"
#include "heap_julia.h"

#define Err printf
#define tagconst 0xDEFF1024
#ifdef _DEBUG
#define Dbg printf
#else
#define Dbg
#endif

#ifdef _DEBUG
void heap_julia::control(int code)
{
	WaitForSingleObject(MutexArr[0],INFINITE);
		int b=0,e=0;
		for (int i=0;i<total_limit_;i++)
	{		if (beginnings[i])
				b++;
			if (ends[i])
				e++;}
		if (b!=e)
		{
		code+=0;
		}

		ReleaseMutex(MutexArr[0]);
}
#endif

 heap_julia::heap_julia( size_t total, alloc_flags flag) : heap876(total, flag, "julia")
 {
	#ifdef _DEBUG
	history = vector<history_struct>();
	history_union u;
	u.constr.total=total;
	u.constr.flag=flag;
	history.push_back(history_struct(constructor_code,u));
	#endif

	if (total>(2 * (1 << 29)))
	{
		#ifdef _DEBUG
		history_union u1;
		u1.message="It is not recommended to use the allocator at volumes more than 2 Gb";
		history.push_back(history_struct(error,u1));
		#endif
		Err("It is not recommended to use the allocator at volumes more than 2 Gb\n");
		total=0;
		throw exception("Wrong size");
	}
	if (total<1)
	{
		#ifdef _DEBUG
		history_union u2;
		u2.message="Wrong size";
		history.push_back(history_struct(error,u2));
	  dump_history();
	  #endif
	  Err("Wrong size %d \n",total);
	  total=0;
	  throw exception("Wrong size");
	}
	
			size_of_block=128*16; //bytes
	//total is measured in bytes
    int i;
	total_limit_=(total+size_of_block-1)/size_of_block;
	total_limit=total;
	
	if (total_limit_>4)
	{
		mutexed_part=mutexed_part_;
		mutex_amount=mutex_amount_;
	}
	else
	{
		mutexed_part=1;
		mutex_amount=3;
	}

	memory = (char*)malloc(total_limit_*size_of_block*sizeof(char));
	if (memory==NULL) 
	{
		#ifdef _DEBUG
		history_union u2;
		u2.message="Can't allocate memory";
		history.push_back(history_struct(error,u2));
		dump_history();
		#endif
		Err("Can't allocate memory\n");
		throw bad_alloc("");
	}
	if (flag&alloc_debug)
	for (i=0;i<(int)total_limit_*size_of_block/4;i++)
	  ((int*)memory)[i]=tagconst;
	//memset(((int*)memory),tagconst,total_limit_*(size_of_block/4));
	bitmask = vector<bool>(total_limit_,false);
	beginnings = vector<bool>(total_limit_,false);
	ends = vector<bool>(total_limit_,false);
	alloc_sz = 0; 
	 if(flag&alloc_tagged)
	{ 
		tagArray= (unsigned int*)malloc(total_limit_*sizeof(unsigned int));
		if (tagArray==NULL) 
		{
			#ifdef _DEBUG
			history_union u2;
			u2.message="Can't allocate memory for tags";
			history.push_back(history_struct(error,u2));
			#endif
			Err("Can't allocate memory for tags\n");
			throw exception("Can't allocate memory");
			return;
		}
		memset(tagArray,tagconst,total_limit_);
	}

	 for (i=0;i<mutex_amount;i++)
	 MutexArr[i]=CreateMutex(NULL,FALSE,NULL);

	  #ifdef _DEBUG
	  if ((log = fopen("log.txt","at")) == 0 ) 
	  { 
		  Err("Unable to create file\n");
	  }
	  fprintf(log,"===================== Log ====================\n");
      #endif
};

heap_julia::~heap_julia() 
{ 
	if( alloc_sz ) 
	{
		#ifdef _DEBUG
		history_union u2;
		u2.message="[heap] destruct not empty";
		history.push_back(history_struct(error,u2));
		#endif
		Err("[heap] destruct not empty %d\n", alloc_sz ); 
	}
	#ifdef _DEBUG
	dump_history();
	fprintf(log,"================== End of Log =================\n");
	fclose(log);
	 #endif
	std::free (memory);
	 if(flag&alloc_tagged)
	std::free(tagArray);
}

#ifdef _DEBUG
void heap_julia::dump_history()
{
	WaitForSingleObject(MutexArr[mutex_amount-1],INFINITE); 
	vector<history_struct>::iterator iter;

	for (iter=history.begin();iter<history.end();iter++)
	switch (iter->code_of_func)
	{
	case constructor_code: fprintf(log,"Constructor: total=0x%x, flag = %d\n",iter->uni.constr.total,iter->uni.constr.flag); break;
	case alloc_code: fprintf(log,"Alloc: allocation size=0x%x, tag = %d\n",iter->uni.alloc__.sz,iter->uni.alloc__.tag);break;
	case free_code: fprintf(log,"Free: address=0x%x\n",iter->uni.free__);break;
	case free_all_code: fprintf(log,"Free all: tag = %d\n",iter->uni.free_all__);break;
	case error: fprintf(log,"Error: %s\n",iter->uni.message);break;
	default: Err ("Unknown code in history");
	}
	ReleaseMutex(MutexArr[mutex_amount-1]);

}
#endif

void* heap_julia::alloc( size_t sz, unsigned int tag )
{  
	#ifdef _DEBUG
	WaitForSingleObject(MutexArr[mutex_amount-1],INFINITE); 
	history_union u;
	u.alloc__.sz=sz;
	u.alloc__.tag=tag;
	history.push_back(history_struct(alloc_code,u));
     #endif

	if( ( alloc_sz + sz ) > total_limit_*size_of_block )
	{
		#ifdef _DEBUG
		history_union u2;
		u2.message="[heap] failed to alloc";
		history.push_back(history_struct(error,u2));
		ReleaseMutex(MutexArr[mutex_amount-1]);
        #endif

		Err("[heap] failed to alloc {sz=%d, tg=0x%x} allocated sz=%d, total=%d\n",
			sz, tag, alloc_sz, total_limit_*size_of_block );

		return NULL;
	}
	#ifdef _DEBUG
	ReleaseMutex(MutexArr[mutex_amount-1]);
    #endif
	int i,j;
	int found_hole_size=0;
	int begin=-1;
	
	WaitForSingleObject(MutexArr[0],INFINITE);

	for (i=0;i<(int)total_limit_;i++)
	{    
		if ((i % (total_limit_ / mutexed_part))==0)
		{
		  if ((i!=0)&&(mutexed_part!=1))
		{	
			ReleaseMutex(MutexArr[i/(total_limit_/mutexed_part)-1]);
			WaitForSingleObject(MutexArr[i/(total_limit_/mutexed_part)],INFINITE);
		}
		}
		bool IsOk=true;
		if (flag&alloc_debug)
		{ 
			for (j=0;j<size_of_block/4;j++)
			if (((int*)memory)[i*size_of_block/4+j]!=tagconst)
				IsOk=false;
		}
		if ((!bitmask[i])&&(( (flag==alloc_tagged&alloc_debug) ?(tagArray[i]!=tagconst) : false)||((flag==alloc_debug) ? !IsOk : false)))
		{
			#ifdef _DEBUG
			WaitForSingleObject(MutexArr[mutex_amount-1],INFINITE); 
			history_union u2;
			u2.message="Someone uses our memory";
			history.push_back(history_struct(error,u2));
			ReleaseMutex(MutexArr[mutex_amount-1]);
			#endif

		  Err("Someone uses our memory at 0x%x\n",&memory[i]);
		  			getchar();
		   if(flag&alloc_tagged)
			tagArray[i]=tagconst;
		  if (flag&alloc_debug)
		  {
			for (j=0;j<size_of_block;j++)
			  ((int*)memory)[i*size_of_block/4+j]=tagconst;
		  }
		}
		found_hole_size= (found_hole_size+(int)!bitmask[i])*((int)!bitmask[i]);
		if (found_hole_size!=0)
		{
			if (begin==-1)
				begin=i; 
		}
		else begin=-1;
		if (found_hole_size*size_of_block >=(int)sz)
		{
			if (mutexed_part!=1)
			ReleaseMutex(MutexArr[i/(total_limit_/mutexed_part)]);
			else ReleaseMutex(MutexArr[0]);
			break;
		}
	}

	if (mutexed_part!=1)
		ReleaseMutex(MutexArr[mutexed_part-1]);
	else ReleaseMutex(MutexArr[0]);

	if (begin==-1)
	{
		#ifdef _DEBUG
		WaitForSingleObject(MutexArr[mutex_amount-1],INFINITE); 
		history_union u2;
		u2.message="Not enough free place";
		history.push_back(history_struct(error,u2));
		Err("Not enough free place\n");
		ReleaseMutex(MutexArr[mutex_amount-1]);
			control(1);
		#endif
		return NULL;
	}

	int mutex_amount_current=(found_hole_size + total_limit_/mutexed_part-1)/(total_limit_/mutexed_part);
	if (mutexed_part!=1)
		for (i=0;i<mutex_amount_current;i++)
		WaitForSingleObject(MutexArr[begin/(total_limit_/mutexed_part)+i],INFINITE);
	else WaitForSingleObject(MutexArr[0],INFINITE);

	for (j=0;j<found_hole_size;j++)
		{	if (bitmask[begin+j])
			{
				if (mutexed_part!=1)
					for (i=0;i<mutex_amount_current;i++)
						ReleaseMutex(MutexArr[begin/(total_limit_/mutexed_part)+i]);
				else ReleaseMutex(MutexArr[0]);
				void* address=alloc(sz,tag );
				return address;
			}
		}


	if (found_hole_size*size_of_block >=(int)sz)
	//if (found!=-1)
	{
		alloc_sz += found_hole_size*size_of_block;
		for (j=0;j<found_hole_size;j++)
		{
			 if(flag&alloc_tagged)
			   tagArray[begin+j]=tag;
			bitmask[begin+j]=true;
		}
		beginnings[begin]=true;
	    ends[begin+found_hole_size-1]=true;
		if (mutexed_part!=1)
		for (i=0;i<mutex_amount_current;i++)
			ReleaseMutex(MutexArr[begin/(total_limit_/mutexed_part)+i]);
		else ReleaseMutex(MutexArr[0]);
		#ifdef _DEBUG
			control(1);
		#endif
		return &memory[begin*size_of_block];
	}
	if (mutexed_part!=1)
	  for (i=0;i<mutex_amount_current;i++)
		  ReleaseMutex(MutexArr[begin/(total_limit_/mutexed_part)+i]);
	else ReleaseMutex(MutexArr[0]);

	  #ifdef _DEBUG
	 WaitForSingleObject(MutexArr[mutex_amount-1],INFINITE); 
	  history_union u2;
	  u2.message="Not enough memory";
	  history.push_back(history_struct(error,u2));
	  ReleaseMutex(MutexArr[mutex_amount-1]);
	  	control(1);
	#endif
	Err("Not enough memory\n");
	return NULL;
}

void heap_julia::print_all()
{
	WaitForSingleObject(MutexArr[mutex_amount-2],INFINITE);
	is_hungry();
	cout << alloc_sz << "sz \n\n";
	int i;
 	for(i=0; i<(int)total_limit_;i++)
		cout << bitmask[i] << " ";
		cout << "\n beginnings \n";
	for(i=0; i<(int)total_limit_;i++)
		cout << beginnings[i] << " ";
	cout << "\n ends \n";
	for(i=0; i<(int)total_limit_;i++)
		cout << ends[i] << " ";
	/*int j;
	cout << "\nmemory\n";
	for(i=0; i<total_limit_;i++)
	{
		for (j=0;j<size_of_block;j++)
			cout <<  memory[i*size_of_block+j]<< " ";
		if (i==0) {getchar();}
	     cout << "\n";
	}*/
	/*for(i=0; i<total_limit_;i++)
	{
		for (j=0;j<size_of_block/4;j++)
			cout <<  (char)(((int*)memory)[(i*size_of_block)/4+j])<< " ";
	     cout << "\n";
	}*/
	
	 if(flag&alloc_tagged)
	{
		cout << "\ntags\n";
	for(i=0; i<(int)total_limit_;i++)
		cout << tagArray[i]<< " ";
	}
	cout << "\n\n";
	ReleaseMutex(MutexArr[mutex_amount-2]);
}

void heap_julia::free( void* ptr )
{
	if (ptr==NULL)
		return;
	 #ifdef _DEBUG
	WaitForSingleObject(MutexArr[mutex_amount-1],INFINITE); 
	history_union u;
	u.free__=ptr;
	history.push_back(history_struct(free_code,u));
	#endif
     //checking if the address is ours
	if (((char*)ptr-memory)% size_of_block !=0)
	{
		 #ifdef _DEBUG
		history_union u2;
		u2.message="No block starting with on given address";
		history.push_back(history_struct(error,u2));
		ReleaseMutex(MutexArr[mutex_amount-1]);
			control(2);
		#endif
			Err("No block starting with on address 0x%x  alloced_sz=%d, total=%d\n",ptr,alloc_sz, total_limit_* size_of_block);
		return;
	}

	int i=((char*)ptr-memory)/size_of_block;
	if ((i<0)||(i>(int)total_limit_))
	{
		 #ifdef _DEBUG
		history_union u2;
		u2.message="[heap] failed to free. Address doesn't belong current memory";
		history.push_back(history_struct(error,u2));
		ReleaseMutex(MutexArr[mutex_amount-1]);

		 	control(2);
		#endif
			Err("[heap] failed to free %x. Address doesn't belong current memory. sz=%d, total=%d\n",ptr,alloc_sz, total_limit_* size_of_block);
		 return;
    }

	if (!beginnings[i])
	{	 
		 #ifdef _DEBUG
		history_union u2;
		u2.message="[heap] failed to free . No piece starting on address is found";
		history.push_back(history_struct(error,u2));
	  ReleaseMutex(MutexArr[mutex_amount-1]);
		#endif
	  Err("[heap] failed to free %x. No piece starting on address %x is found. sz=%d, total=%d\n",ptr,ptr,alloc_sz, total_limit_* size_of_block);
	  
	  return;
	}

	 #ifdef _DEBUG
	ReleaseMutex(MutexArr[mutex_amount-1]);
    #endif
	int end=-1,j;
	for (j=i;j<(int)total_limit_;j++)
		if (ends[j])
		{
			end=j;
	        break;
		}

	if (end==-1)
	{
		if(flag&alloc_tagged)
			Err("Error 1: there is no end of block  %x tag = %d sz=%d, total=%d\n",ptr,tagArray[i],alloc_sz, total_limit_* size_of_block);
		else 
			Err("Error 1: there is no end of block  %x sz=%d, total=%d\n",ptr,alloc_sz, total_limit_* size_of_block);
		
		 #ifdef _DEBUG
		WaitForSingleObject(MutexArr[mutex_amount-1],INFINITE); 
		history_union u2;
		u2.message="Error 1: there is no end of block";
		history.push_back(history_struct(error,u2));
			ReleaseMutex(MutexArr[mutex_amount-1]);
		#endif
			return;
	}

	int mutex_amount_current=(end+1-i + (total_limit_/mutexed_part)-1)/(total_limit_/mutexed_part);
	if (mutexed_part!=1)
	for (int k=0;k<mutex_amount_current;k++)
		WaitForSingleObject(MutexArr[i/(total_limit_/mutexed_part)+k],INFINITE);
	else WaitForSingleObject(MutexArr[0],INFINITE);

	for (j=i;j<end+1;j++)
	{
		if (flag&alloc_debug)
		{
			for (int k=0;k<size_of_block/4;k++)
			 ((int*)memory)[j*size_of_block/4+k]=tagconst;
		}
		 if(flag&alloc_tagged)
			tagArray[j]=tagconst;
		 if (bitmask[j]!=false)
		alloc_sz-=size_of_block;
		bitmask[j]=false;
	}
	beginnings[i]=false;
	ends[end]=false;
	if (mutexed_part!=1)
	 for (int k=0;k<mutex_amount_current;k++)
		 ReleaseMutex(MutexArr[i/(total_limit_/mutexed_part)+k]);
	else ReleaseMutex(MutexArr[0]);
	 #ifdef _DEBUG
	 	control(2);
	#endif
	return;
};


void heap_julia::free_all( unsigned int tag )
{
	 #ifdef _DEBUG
	WaitForSingleObject(MutexArr[mutex_amount-1],INFINITE);		
	history_union u;
	u.free_all__=tag;
	history.push_back(history_struct(free_all_code,u));
	#endif
	if (flag!=alloc_tagged)
	{
		 #ifdef _DEBUG
		history_union u2;
		u2.message="Function is not available";
		history.push_back(history_struct(error,u2));
		ReleaseMutex(MutexArr[mutex_amount-1]);
			control(3);
		#endif
			Err("Function is not available\n");
		return;
	}
	#ifdef _DEBUG
	ReleaseMutex(MutexArr[mutex_amount-1]);
#endif

	int i;
	bool found=false;

	WaitForSingleObject(MutexArr[0],INFINITE);
	for (i=0; i<(int)total_limit_;i++)
	{
		if (i % (total_limit_ / mutexed_part)==0)
		{
		  if ((i!=0)&&(mutexed_part!=1))
		{	
			ReleaseMutex(MutexArr[i/(total_limit_/mutexed_part)-1]);
		   WaitForSingleObject(MutexArr[i/(total_limit_/mutexed_part)],INFINITE);
		 }
		}

		if (tag==tagArray[i])
		{
		 if (flag&alloc_debug)
		 { 
			for (int k=0;k<size_of_block/4;k++)
			 ((int*)memory)[i*size_of_block/4+k]=tagconst;
		 }
		  if(flag&alloc_tagged)
		  tagArray[i]=tagconst;
		  if (bitmask[i]!=false)
		{
		bitmask[i]=false;
		 alloc_sz-=size_of_block;
		  }
		 found=true;
		 beginnings[i]=false;
	     ends[i]=false;
		}
	}

	ReleaseMutex(MutexArr[mutexed_part-1]);

	if (!found)
	{
		#ifdef _DEBUG
		WaitForSingleObject(MutexArr[mutex_amount-1],INFINITE); 
		history_union u2;
		u2.message="[heap] failed to free at tag";
		history.push_back(history_struct(error,u2));
		ReleaseMutex(MutexArr[mutex_amount-1]);
			control(3);
		#endif
			Err("[heap] failed to free at tag %d. sz=%d, total=%d\n",tag ,alloc_sz, total_limit_* size_of_block);
		return;
	}
	#ifdef _DEBUG
		control(3);
#endif
}

void heap_julia::is_hungry()
{
	if (flag!=alloc_tagged)
	{
		#ifdef _DEBUG
		WaitForSingleObject(MutexArr[mutex_amount-1],INFINITE); 
		history_union u2;
		u2.message="Function is not available";
		history.push_back(history_struct(error,u2));
		ReleaseMutex(MutexArr[mutex_amount-1]);
		#endif
		Err("Function is not available\n");
		return;
	}

	if (alloc_sz==0)
	{
		#ifdef _DEBUG
		WaitForSingleObject(MutexArr[mutex_amount-1],INFINITE); 
		history_union u2;
		u2.message="Nothing is allocated";
		history.push_back(history_struct(error,u2));
	   ReleaseMutex(MutexArr[mutex_amount-1]);
		#endif
	    Err("Nothing is allocated\n");
		return;
	}
	struct tags_str
	{ 
	  unsigned int tag;
	  unsigned int amount;
	  tags_str(unsigned int tag_,unsigned int amount_) : tag(tag_), amount(amount_) {};
	};

	tags_str* tags=(tags_str*)malloc(sizeof(tags_str)*total_limit_);
	int i;
	for (i=0;i<(int)total_limit_;i++)
		tags[i].amount=0;
	int j=-1,cur_tag=0;
	for (i=0;i<(int)total_limit_;i++)
	{ 
		if (bitmask[i]==0)
			continue;
		tags[cur_tag].tag=tagArray[i];
		tags[cur_tag].amount=1;
		j=i;
		break;
	}

	if (mutexed_part!=1)
	for (int k=0;k<mutexed_part;k++)
		WaitForSingleObject(MutexArr[k],INFINITE);
	else WaitForSingleObject(MutexArr[0],INFINITE);

	for (i=1+j;i<(int)total_limit_;i++)
	{ 
		if (bitmask[i]==0)
			continue;

		if (tagArray[i]==tagArray[i-1])
		{  
			tags[cur_tag].amount++;
			continue;
		}

		bool increased=false;
		for (j=0;j<=cur_tag;j++)
		if (tagArray[i]==tags[j].tag)
			{
				cur_tag=j;
				tags[j].amount++;
				increased=true;
				break;
		    }
		if (increased)
			continue;
		cur_tag++;
		tags[cur_tag].tag=tagArray[i];
		tags[cur_tag].amount=1;
	}

	int max=-1,max_tag=-1;
	for (j=0;j<=(int)total_limit_;j++)
	{
		if (tags[j].amount==0)
			break;
		if (max < (int)tags[j].amount)
		{
		  max=tags[j].amount;
		  max_tag=tags[j].tag;
		}
	}

	if (mutexed_part!=1)
	for (int k=0;k<mutexed_part;k++)
		ReleaseMutex(MutexArr[k]);
	else ReleaseMutex(MutexArr[0]);

	cout << max_tag << " is the most hungry\n";
}

size_t heap_julia::get_volume() 
{
	return (total_limit_*size_of_block);
}